/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr || head->next == nullptr)
            return head;
        
        ListNode dummy(0, head);
        ListNode *part = head, *partPrev = &dummy;
        while(part != nullptr && part->val < x)
        {
            partPrev = part;
            part = part->next;
        }

        // part走到最后了，说明不用分割
        if(part == nullptr)
            return head;

        ListNode *cur = part->next, *prev = part;
        while(cur != nullptr)
        {
            ListNode *next = cur->next;
            if(cur->val < x)
            {
                // 在part处头插
                prev->next = cur->next;
                cur->next = part;
                partPrev->next = cur;
                partPrev = cur;
            }
            else
            {
                prev = cur;
            }
            cur = next;
        }
        return dummy.next;
    }
};